package cn.camel.algorithm.tree.avl;

/**
 * @author: Camel
 * @description: AVL树实现类
 * AVL树是一种自平衡二叉搜索树，通过旋转操作保持平衡
 * 平衡条件：任意节点的左右子树高度差不超过1
 * @date: 2025/10/15
 */
public class AVLTree {
    /** 根节点 */
    private AVLNode root;

    /**
     * 构造函数，初始化空的AVL树
     */
    public AVLTree() {
        this.root = null;
    }

    /**
     * 获取节点的高度
     * 如果节点为空，返回0
     * @param node 要获取高度的节点
     * @return 节点的高度
     */
    private int height(AVLNode node) {
        if (node == null) {
            return 0;
        }
        return node.getHeight();
    }

    /**
     * 获取节点的平衡因子
     * 平衡因子 = 左子树高度 - 右子树高度
     * @param node 要计算平衡因子的节点
     * @return 平衡因子
     */
    private int getBalance(AVLNode node) {
        if (node == null) {
            return 0;
        }
        return height(node.getLeft()) - height(node.getRight());
    }

    /**
     * 更新节点的高度
     * 节点高度 = 1 + 左右子树高度的最大值
     * @param node 要更新高度的节点
     */
    private void updateHeight(AVLNode node) {
        if (node != null) {
            int leftHeight = height(node.getLeft());
            int rightHeight = height(node.getRight());
            node.setHeight(Math.max(leftHeight, rightHeight) + 1);
        }
    }

    /**
     * 右旋操作（左左情况）
     * 用于处理左子树过高的不平衡情况
     * @param y 不平衡的节点
     * @return 旋转后的新根节点
     */
    private AVLNode rightRotate(AVLNode y) {
        AVLNode x = y.getLeft();
        AVLNode T2 = x.getRight();

        // 执行旋转
        x.setRight(y);
        y.setLeft(T2);

        // 更新高度
        updateHeight(y);
        updateHeight(x);

        return x;
    }

    /**
     * 左旋操作（右右情况）
     * 用于处理右子树过高的不平衡情况
     * @param x 不平衡的节点
     * @return 旋转后的新根节点
     */
    private AVLNode leftRotate(AVLNode x) {
        AVLNode y = x.getRight();
        AVLNode T2 = y.getLeft();

        // 执行旋转
        y.setLeft(x);
        x.setRight(T2);

        // 更新高度
        updateHeight(x);
        updateHeight(y);

        return y;
    }

    /**
     * 插入新节点到AVL树
     * @param val 要插入的值
     */
    public void insert(int val) {
        root = insert(root, val);
    }

    /**
     * 递归插入新节点并保持平衡
     * @param node 当前节点
     * @param val 要插入的值
     * @return 插入后的节点
     */
    private AVLNode insert(AVLNode node, int val) {
        // 1. 执行标准的BST插入
        if (node == null) {
            return new AVLNode(val);
        }

        if (val < node.getVal()) {
            node.setLeft(insert(node.getLeft(), val));
        } else if (val > node.getVal()) {
            node.setRight(insert(node.getRight(), val));
        } else {
            // 不允许重复值
            return node;
        }

        // 2. 更新当前节点的高度
        updateHeight(node);

        // 3. 获取平衡因子检查是否平衡
        int balance = getBalance(node);

        // 4. 如果不平衡，有四种情况需要处理

        // 左左情况（左子树的左子树过高）
        if (balance > 1 && val < node.getLeft().getVal()) {
            return rightRotate(node);
        }

        // 右右情况（右子树的右子树过高）
        if (balance < -1 && val > node.getRight().getVal()) {
            return leftRotate(node);
        }

        // 左右情况（左子树的右子树过高）
        if (balance > 1 && val > node.getLeft().getVal()) {
            node.setLeft(leftRotate(node.getLeft()));
            return rightRotate(node);
        }

        // 右左情况（右子树的左子树过高）
        if (balance < -1 && val < node.getRight().getVal()) {
            node.setRight(rightRotate(node.getRight()));
            return leftRotate(node);
        }

        // 如果平衡，直接返回节点
        return node;
    }

    /**
     * 从AVL树中删除指定值的节点
     * @param val 要删除的值
     */
    public void delete(int val) {
        root = delete(root, val);
    }

    /**
     * 递归删除节点并保持平衡
     * @param node 当前节点
     * @param val 要删除的值
     * @return 删除后的节点
     */
    private AVLNode delete(AVLNode node, int val) {
        // 1. 执行标准的BST删除
        if (node == null) {
            return null;
        }

        if (val < node.getVal()) {
            node.setLeft(delete(node.getLeft(), val));
        } else if (val > node.getVal()) {
            node.setRight(delete(node.getRight(), val));
        } else {
            // 找到要删除的节点

            // 节点只有一个子节点或没有子节点
            if (node.getLeft() == null || node.getRight() == null) {
                AVLNode temp = null;
                if (temp == node.getLeft()) {
                    temp = node.getRight();
                } else {
                    temp = node.getLeft();
                }

                // 没有子节点的情况
                if (temp == null) {
                    temp = node;
                    node = null;
                } else {
                    // 有一个子节点的情况
                    node = temp;
                }
            } else {
                // 节点有两个子节点：获取中序后继（右子树的最小值）
                AVLNode temp = minValueNode(node.getRight());
                node.setVal(temp.getVal());
                node.setRight(delete(node.getRight(), temp.getVal()));
            }
        }

        // 如果树只有一个节点，直接返回
        if (node == null) {
            return null;
        }

        // 2. 更新当前节点的高度
        updateHeight(node);

        // 3. 获取平衡因子检查是否平衡
        int balance = getBalance(node);

        // 4. 如果不平衡，有四种情况需要处理

        // 左左情况
        if (balance > 1 && getBalance(node.getLeft()) >= 0) {
            return rightRotate(node);
        }

        // 左右情况
        if (balance > 1 && getBalance(node.getLeft()) < 0) {
            node.setLeft(leftRotate(node.getLeft()));
            return rightRotate(node);
        }

        // 右右情况
        if (balance < -1 && getBalance(node.getRight()) <= 0) {
            return leftRotate(node);
        }

        // 右左情况
        if (balance < -1 && getBalance(node.getRight()) > 0) {
            node.setRight(rightRotate(node.getRight()));
            return leftRotate(node);
        }

        return node;
    }

    /**
     * 查找子树中的最小值节点
     * @param node 子树根节点
     * @return 最小值节点
     */
    private AVLNode minValueNode(AVLNode node) {
        AVLNode current = node;
        while (current.getLeft() != null) {
            current = current.getLeft();
        }
        return current;
    }

    /**
     * 在AVL树中查找指定值
     * @param val 要查找的值
     * @return 如果找到返回true，否则返回false
     */
    public boolean search(int val) {
        return search(root, val);
    }

    /**
     * 递归查找指定值
     * @param node 当前节点
     * @param val 要查找的值
     * @return 如果找到返回true，否则返回false
     */
    private boolean search(AVLNode node, int val) {
        if (node == null) {
            return false;
        }

        if (val == node.getVal()) {
            return true;
        } else if (val < node.getVal()) {
            return search(node.getLeft(), val);
        } else {
            return search(node.getRight(), val);
        }
    }

    /**
     * 中序遍历AVL树
     * 对于AVL树，中序遍历会产生有序序列
     */
    public void inorder() {
        inorder(root);
        System.out.println();
    }

    /**
     * 递归执行中序遍历
     * @param node 当前节点
     */
    private void inorder(AVLNode node) {
        if (node != null) {
            inorder(node.getLeft());
            System.out.print(node.getVal() + "(" + node.getHeight() + ") ");
            inorder(node.getRight());
        }
    }

    /**
     * 前序遍历AVL树
     */
    public void preorder() {
        preorder(root);
        System.out.println();
    }

    /**
     * 递归执行前序遍历
     * @param node 当前节点
     */
    private void preorder(AVLNode node) {
        if (node != null) {
            System.out.print(node.getVal() + "(" + node.getHeight() + ") ");
            preorder(node.getLeft());
            preorder(node.getRight());
        }
    }

    /**
     * 检查AVL树是否平衡
     * @return 如果平衡返回true，否则返回false
     */
    public boolean isBalanced() {
        return isBalanced(root);
    }

    /**
     * 递归检查子树是否平衡
     * @param node 当前节点
     * @return 如果平衡返回true，否则返回false
     */
    private boolean isBalanced(AVLNode node) {
        if (node == null) {
            return true;
        }

        int balance = getBalance(node);
        if (Math.abs(balance) > 1) {
            return false;
        }

        return isBalanced(node.getLeft()) && isBalanced(node.getRight());
    }

    /**
     * 获取树的高度
     * @return 树的高度
     */
    public int getHeight() {
        return height(root);
    }

    /**
     * 获取根节点
     * @return 根节点
     */
    public AVLNode getRoot() {
        return root;
    }

    /**
     * 主方法，用于测试AVL树的功能
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        AVLTree tree = new AVLTree();

        // 测试插入操作
        System.out.println("插入节点序列: 10, 20, 30, 40, 50, 25");
        tree.insert(10);
        tree.insert(20);
        tree.insert(30);
        tree.insert(40);
        tree.insert(50);
        tree.insert(25);

        // 测试遍历
        System.out.print("中序遍历结果: ");
        tree.inorder();

        System.out.print("前序遍历结果: ");
        tree.preorder();

        // 测试查找
        System.out.println("查找值30: " + tree.search(30));
        System.out.println("查找值35: " + tree.search(35));

        // 测试平衡检查
        System.out.println("树是否平衡: " + tree.isBalanced());
        System.out.println("树的高度: " + tree.getHeight());

        // 测试删除操作
        System.out.println("删除节点10");
        tree.delete(10);

        System.out.print("删除后的中序遍历: ");
        tree.inorder();

        System.out.println("删除后树是否平衡: " + tree.isBalanced());
        System.out.println("删除后树的高度: " + tree.getHeight());

        // 测试更多插入操作
        System.out.println("插入更多节点: 5, 15, 35, 45");
        tree.insert(5);
        tree.insert(15);
        tree.insert(35);
        tree.insert(45);

        System.out.print("最终中序遍历: ");
        tree.inorder();
        System.out.println("最终树是否平衡: " + tree.isBalanced());
    }
}